import java.util.Arrays;

public class 最接近目标值的子序列和 {

    public static int MAXM = 21;
    public int[] lsum = new int[MAXM];
    public int[] rsum = new int[MAXM];
    public int j;
    public int minAbsDifference(int[] nums, int goal) {
        int n = nums.length;
        j = 0;
        int max = 0;
        int min = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] >= 0) {
                max += nums[i];
            } else {
                min += nums[i];
            }
        }
        if (max <= goal) return goal - max;
        if (min >= goal) return min - goal;
        Arrays.sort(nums);
        dfs (0,n / 2,0,lsum,nums);
        int lsize = j;
        j = 0;
        dfs (n / 2,n,0,rsum,nums);
        int rsize = j;
        int a = 0;
        int b = rsize - 1;
        while (a < lsize && b >= 0) {
            if (lsum[a] + rsum[b])
        }
    }

    private void dfs(int a, int b,int v, int[] ans,int[] nums) {
        if (a == b) {
            ans[j++] = v;
        } else {
            int k = a + 1;
            while (k < b && nums[a] == nums[k]) {
                k++;
            }
            for (int i = 0; i <= k - a; i++) {
                dfs(a + 1,b,v + i * nums[a],ans,nums);
            }
        }
    }
}
